pub fn dp_rec_mc(amount: u32) -> u32 {
    min_count(amount)
}

// 实现⼀个算法，⽤于实现最⼩找零纸币数。币种含：1、2、5、10、20、30、50、100元。
// 贪心算法有时会得不到最优解，我们使用动态规划算法
fn min_count(amount: u32) -> u32 {
    // 定义面额数组
    let values = [1u32, 2, 5, 10, 20, 30, 50, 100];

    // 建立最优解的数组, 设置为u32类型的最大值
    let mut min = vec![std::u32::MAX; amount as usize + 1];
    min[0] = 0; // 索引0出设置为0

    // 遍历从1到amount所有数值的最优解,采用自底向上的方法, 上面的最优解是基于下面的最优解的思路
    for i in 1..=amount {
        for v in values {
            if i >= v {
                let min_value = u32::min(min[i as usize], min[(i - v) as usize] + 1);
                min[i as usize] = min_value;
            }
        }
    }

    min[amount as usize]
}
